Huge Graph Visualization

% Remco Bloemen % 2014-05-07

\newcommand{\bindingOperator}[3]{\mathrm{#1}^{#3}_{#2}} \newcommand{\set}[1]{\mathcal #1} \newcommand{\Σ}[2][]{\bindingOperator{{\scriptstyle\raise{.2em}\sum}}{#1}{#2}}

The plan

Rapid Graph Layout Using Space Filling Curves http://vis.cs.ucdavis.edu/papers/muelder_ma_rgl_2008.pdf Network data frequently arises in a wide variety of fields, and node-link diagrams are a very natural and intuitive represen- tation of such data. In order for a node-link diagram to be effective, the nodes must be arranged well on the screen. While many graph layout algorithms exist… Large-Scale Graph Visualization and Analytics http://vis.cs.ucdavis.edu/papers/computer2013-graphvis.pdf Novel approaches to network visualization and analytics use sophisticated metrics that enable rich interactive network views and node grouping and filtering. A survey of graph layout and simplification methods reveals considerable progress in these new directions. "Fast Modularity" Community Structure Inference Algorithm http://cs.unm.edu/~aaron/research/fastmodularity.htm This page documents and supports the fast modularity maximization algorithm I developed jointly with Mark Newman and Cristopher Moore. This algorithm is being widely used in the community of complex network researchers…

The Peano-Gosper curve

Producing the curve

The matrix

$$ \frac{1}{14} \begin{bmatrix} -\sqrt{3} & 5 \\ 0.2474 & 4 \end{bmatrix} $$

The source

static const double CAsin = -0.12371791482634837810910331010756231192448608955788433057541; // -sqrt(3) / 14
static const double CAcos = 5.0 / 14.0;
static const double CBsin = 0.247435829652696756218206620215124623848972179115768661150829;
static const double CBcos = 2.0 / 7.0;

The Flowsnake in C++

Aperiodic space-filling curves?

Write a curve in recursive aperiodic titles? https://en.wikipedia.org/wiki/Penrose_tiling

Alternative:

Place points using Poisson disk. Create a weighted graph out of the distances. Apply linearisation to the weight matrix. Now the points are sorted and can be used as in the space-filling case.

https://en.wikipedia.org/wiki/Low-discrepancy_sequence

Full graph

This reminds me of electron diffraction patterns in crystals, also very beautiful.

Right, back to our main goal.

Locality

The graph has roughly 17 thousand nodes and 34 thousand edges.

Test data

Walktrap ordering

Balancing the binary tree

Let’s now look at the community hierarchy:

Sorting the binary tree

Separating the communities

Compared to the first plot, the community structure suffered from sorting, because now the interacting communities are forced closer together.

TODO:

Remco Bloemen
Math & Engineering
https://2π.com